1. Field of the Invention
This invention relates to components of a data processing system and, more particularly, to data processing system multiplier components. The data processing system multiplier components multiply a multiplicand represented by data bits by a multiplier represented by data bits.
2. Description of the Related Art
In the related art, multiplier units, such as the booth multiplier unit or the parallel multiplier unit, typically have a low utilization of components. This low utilization is the result of the time for data to ripple through the multiplier unit. In both of the cited multiplier configurations, the ripple time results from the time for the data to be processed by the summation stage of the multiplier unit. In the past, in order to reduce the ripple time, carry look-ahead circuits have been implemented. However, the implementation of carry look-ahead circuits provides a significant increase in the complexity and number of components needed for the multiplier unit.
Referring to FIG. 1, the multiplier unit for the multiplication of a binary multiplicand A by a binary multiplier B unit can typically be divided into three stages. The first stage is a preprocessing of multiplicand A stored in register 10 by preprocessor stage 11 to simplify the apparatus used to implement the multiplication procedure. The digit generator component 13 next provides the i.sup.th digit of the multiplier B stored in register 20, i.e., B.sub.i. The product A*B.sub.i is generated in the second stage or the multiplier stage 12. In the third stage or the summation stage 14, the sum of A*B.sub.i is generated, this partial product being shifted by S.sub.i, i.e., the position of the multiplier bit B.sub.i in the multiplier register 20. The operation of these three stages generate the desired result because B=SUM(i){B.sub.i 2.sup.Si }. For example, in a simple shift and add multiplier unit, the preprocessor stage 11 is inactive. The multiplier stage 12 multiplies A by either 1 or 0, this binary bit being the i.sup.th digit of B. The summation stage 14 shifts the products by S.sub.i and adds all the results together.
In this example, most of the complexity is in the third or summation stage. The second or multiplier stage is relatively simple because the "digits" of the multiplier are either 1 or 0. The utilization of the adder components is low because in third or summation stage 14, the additions take place serially and are added to a single running sum. However, in many instances of multiplier units, a longer time for performing the multiplication function can be tolerated when fewer components are needed to perform the multiplication operation.
A need has therefore been felt for apparatus and a related method to provide for a higher utilization of the components of the multiplier unit. The higher component utilization results in a greater number of processing cycles to implement a multiplication procedure. In addition, it is further desirable that much of the addition of partial products be performed in the second or multiplier stage resulting in relatively little carry-ripple activity in the third or summation stage.